package com.zzw.algorithm.tree;

import org.junit.Test;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * created by zzw
 */
//层次遍历 对树的每一层节点进行遍历
public class ArrangementTree<K,V> {

    private TreeNode<K, V> root;


    public void createTree(List<K> keys, List<V> values) throws Exception {
        Queue<TreeNode<K,V>> queue = new LinkedList<TreeNode<K,V>>();
        // 如果两个列表大小不一样或者为空，抛出异常
        if (keys.size() != values.size() && keys.isEmpty() && values.isEmpty())
            throw new Exception("Inputs' scale are not equal.");
        // 如果root为空，创建root
        if (root == null)
            root = new TreeNode<K,V>(keys.get(0), values.get(0));
        TreeNode<K,V> p = root;
        // 创建树结构
        for (int i = 1; i < keys.size(); i ++) {
            // 如果节点为空，寻找下一个不为空的节点，回滚i的值
            if (p == null && !queue.isEmpty()) {
                p = queue.poll();
                i --;
                continue;
            }
            if (p.left == null) {
                p.left = new TreeNode<K,V>(keys.get(i), values.get(i));
                queue.offer(p.left);
            } else if (p.right == null) {
                p.right = new TreeNode<K,V>(keys.get(i), values.get(i));
                queue.offer(p.right);
            } else {
                if (!queue.isEmpty()) {
                    // 如果节点有左右子树，寻找下一个节点，回滚i的值
                    p = queue.poll();
                    i --;
                }
            }
        }
    }

    //非递归
    public void levelorder() {
        Queue<TreeNode<K,V>> queue = new LinkedList<TreeNode<K,V>>();
        if (root == null) return;
        queue.offer(root);
        while (!queue.isEmpty()) {
            for (int i = queue.size() - 1; i >= 0; i --) {
                TreeNode<K,V> p = queue.poll();
                if (p.left != null) queue.offer(p.left);
                if (p.right != null) queue.offer(p.right);
                System.out.print(p.toString() + " ");
            }
            System.out.println("");
        }
    }

    //递归
    public void levelorder2(List<List> res, TreeNode root, int depth) {
        if (root == null) return;
        if(res.size() <= depth){
           res.add(new LinkedList<>());
        }
        res.get(depth).add(root.getValue());
        levelorder2(res,root.left,depth + 1);
        levelorder2(res,root.right,depth + 1);
    }

    @Test
    public void levelorderTest() throws Exception {
        List<Integer> keys = new ArrayList<Integer>();
        List<String> values = new ArrayList<String>();
        for (int i = 0; i < 10; i ++) {
            keys.add(i);
            values.add(i + "");
        }
        ArrangementTree<Integer, String> tree = new ArrangementTree<Integer, String>();
        tree.createTree(keys, values);
        tree.levelorder();
        /*List<List> objects = new LinkedList<>();
        tree.levelorder2(objects,tree.root,0);

        for (List list:objects){
            for (Object o:list){
                System.out.println(o);
            }
        }*/
    }
}
